2524. Строки Фибоначчи

 

В математике достаточно часто применяются так называемые рекуррентные соотношения. Обычно они применяются для задания числовых последовательностей, но могут применяться и для задания последовательностей строк.

Одним из примеров строк, задаваемых рекуррентным соотношением являются строки Фибоначчи F0 = a, F1 = b, ... . Они задаются следующим образом: F0 = a, F1 = b, Fi = Fi–2Fi–1, i > 1. Первые семь строк Фибоначчи выглядят следующим образом: a, b, ab, bab, abbab, bababbab, abbabbababbab.

Дима занимается в кружке олимпиадного программирования и интересуется алгоритмами на строках. Недавно он узнал о строках Фибоначчи. Он быстро понял, что их длина с увеличением номера n растет очень быстро, поэтому задача нахождения всех символов строки Fn требует слишком большого объема памяти. Поэтому он решил ограничиться задачей нахождения некоторых символов.

Напишите программу, которая находит k-ый символ строки Fn.

 

Вход. Первая строка содержит количество тестов t (1 ≤ t ≤ 100). Каждая из следующих t строк содержит два целых числа n и k (0 ≤ n ≤ 45, 1 ≤ k ≤ |Fn|, через |Fn| обозначена длина строки Fn, позиции символов в строке нумеруются с единицы).

 

Выход. Выведите t строк, каждая из которых содержит k-ый символ строки Fn.

 

Пример входа

Пример выхода

 
4
0 1
1 1
3 2

7 7

a

b

a

a

 

 

РЕШЕНИЕ

рекурсия, строки

 

Анализ алгоритма

Используя тот факт, что Fn = Fn–2Fn–1, будем искать k-ый символ либо в Fn–2, либо в Fn–1. Если k ≤ |Fn–2|, то k-ый символ лежит в Fn–2, иначе в Fn–1.

 

Пример

Обозначим через Fn(k) k-ый символ Fn.

Тогда Fn(k) = Fn-2(k), если k ≤ |Fn–2|. Иначе Fn(k) = Fn-1(k – |Fn–2|).

Например F6(4) = F4(4), F6(7) = F5(7 – 5) = F5(2).

 

Реализация алгоритма

В массив fib занесем числа Фибоначчи: fib[i] содержит длину Fi.

 

#define MAX 44

int fib[MAX] = {1, 1};

 

Функция solve находит k-ый символ в строке Фибоначчи Fn. Отдельно обрабатываем случаи n = 0 и n = 1.

 

char solve(int n, int k)

{

  if (n == 0) return 'a';

  if (n == 1) return 'b';

 

Известно, что Fn = Fn–2Fn–1. Если k ≤ Fn–2, то k-ый символ лежит в Fn–2. Иначе в Fn–1. То есть при k ≤ Fn–2 следует искать k-ый символ в Fn–2. В противном случае следует искать (k – Fn–2) -ый символ в Fn–1.

 

  if (k <= fib[n-2]) return solve(n - 2, k);

  return solve(n - 1, k - fib[n-2]);

}

 

Основная часть программы. Вычисляем первые MAX чисел Фибоначчи.

 

for(int i = 2; i < MAX; i++)

  fib[i] = fib[i-1] + fib[i-2];

 

Читаем входные данные. Вычисляем и выводим ответ.

 

scanf("%d",&tests);

while(tests--)

{

  scanf("%d %d",&n,&k);

  printf("%c\n",solve(n,k));

}